import java.util.*;

public class GreedyAlgorithmKruskal extends PathAlg {
	public void runAlgorithm() {
		// List to store the final tree
		LinkedList<Edge> tree = new LinkedList<Edge>();

		// List to store the final path, to be returned from the algorithm
		LinkedList<Integer> path = new LinkedList<Integer>();

		// For our particular case, we also need to keep track of the number 
		// of outgoing edges from every node, since we want a path, and not
		// a general path. Also, we can use this to originate the path from
		// node 1.
		HashMap<Integer, Integer> edgeCount = new HashMap<Integer, Integer>();

		// Set up queue
		PriorityQueue<Edge> pQueue = new PriorityQueue<Edge>();

		for(int row=0; row<costs.length; ++row)
		{
			for(int cell=row+1; cell<costs[row].length; ++cell)
			{
				pQueue.offer(new Edge(row, cell));
			}
		}

		// Create Union-Find
		UnionFind uf = new UnionFind(costs.length);

		// Start Kruskal's!!
		while(tree.size() < costs.length-1)
		{
			Edge e = pQueue.poll();
			int[] nodes = e.getNodes();

			/*	Here, we divert from running a pure Kruskal.		*/
			final boolean node0HasAny = edgeCount.get(nodes[0]) != null;
			final boolean node1HasAny = edgeCount.get(nodes[1]) != null;

			// Make sure no node has more than 2 outgoing edges
			if(node0HasAny && edgeCount.get(nodes[0]) > 1)
				continue;
			else if(node1HasAny &&edgeCount.get(nodes[1]) > 1)
				continue;
			// Make sure the start node only has 1 outgoing edge
			else if(nodes[0] == 0 && node0HasAny)
				continue;
			else if(nodes[1] == 0 && node1HasAny)
				continue;


			/*	Back to kruskal. 									*/
			if(!uf.sameSet(nodes[0], nodes[1]))
			{
				uf.setUnion(nodes[0], nodes[1]);
				tree.add(e);

				if(node0HasAny)
					edgeCount.put(nodes[0], 2);
				else
					edgeCount.put(nodes[0], 1);

				if(node1HasAny)
					edgeCount.put(nodes[1], 2);
				else
					edgeCount.put(nodes[1], 1);
			}
		}

		// Construct path
		path.add(0);
		while(tree.size() > 0)
		{
			int last = path.get(path.size()-1);
			for(Edge e : tree)
			{
				int[] nodes = e.getNodes();
				if(nodes[0] == last)
				{
					tree.remove(e);
					path.add(nodes[1]);
					break;
				}
				else if(nodes[1] == last)
				{
					tree.remove(e);
					path.add(nodes[0]);
					break;
				}
			}
		}

		Integer[] p = path.toArray(new Integer[path.size()]);
		this.path = new int[path.size()];
		for(int i=0; i<p.length; ++i)
			this.path[i] = p[i];
	}
	
	public String getName() {
	    return "Kruskal";
    }

	/**
	 *	Simple weighted undirected edge representation
	 */
	private class Edge implements Comparable<Edge> {
		private int n1, n2;
		private double w;

		public Edge(int n1, int n2)
		{
			this.n1 = n1;
			this.n2 = n2;
			this.w  = costs[n1][n2] / (0.5 * probabilities[n1] * probabilities[n2]);
		}
		public int[] getNodes() { return new int[]{n1,n2}; }
		public int compareTo(Edge other)
		{
			double diff = this.w - other.w;

			if(diff == 0)
				return 0;
			else if(diff < 0)
				return -1;
			else
				return 1;
		}
	}

	
	/**
	 * Union-Find datastructure.
	 */
	private class UnionFind {
		// Bottom-to-top tree structure
		private class Record
		{
			int id;
			int size;
			Record parent = null;

			public Record(int id)
			{
				this.id = id;
			}
			public int getId()
			{
				return this.id;
			}

			public void addToSize(int size)
			{
				this.size += size;
			}
			public int getSize()
			{
				return this.size;
			}

			public void setParent(Record parent)
			{
				this.parent = parent;
				parent.addToSize(this.size);
			}
			public Record getParent()
			{
				return this.parent;
			}

			public boolean equals(Object other)
			{
				if(other == null || getClass() != other.getClass() ) {
					return false;
				}
				else {
					Record o = (Record) other;
					return id == o.getId();
				}
			}
		}

		private ArrayList<Record> records = new ArrayList<Record>();
		private HashMap<Integer, Record> recordMap = new HashMap<Integer, Record>();
		
		public UnionFind(int count)
		{
			for(int i=0; i<count; ++i)
			{
				Record r = new Record(i);
				records.add(r);
				recordMap.put(i, r);
			}
		}

		public void setUnion(int x, int y)
		{
			setUnion(recordMap.get(x), recordMap.get(y));
		}
		public void setUnion(Record x, Record y)
		{
			Record xRoot = find(x);
			Record yRoot = find(y);

			if(xRoot.getSize() > yRoot.getSize())
			{
				yRoot.setParent(xRoot);
			}
			else
			{
				xRoot.setParent(yRoot);
			}
		}

		public Record find(Record rec)
		{
			if(rec.getParent() == null)
			{
				return rec;
			}
			else
			{
				rec.setParent(find(rec.getParent()));
				return rec.getParent();
			}
		}
		
		public boolean sameSet(int x, int y)
		{
			return sameSet(recordMap.get(x), recordMap.get(y));
		}
		public boolean sameSet(Record x, Record y)
		{
                return find(x).equals(find(y));
        }
	}
}
